public class Leetcode33 {
    public int search(int[] nums, int target) {
        int len = nums.length;
        int rightVal = nums[len-1];
        int mid = len/2;
        if(len==2){
            if(nums[0]==target){
                return 0;
            }
            if(nums[1]==target){
                return 1;
            }
            return -1;
        }
        if(rightVal<nums[mid]){
            while(rightVal<nums[mid]&&mid<len){
                mid++;
            }
        }else{
            while(rightVal>nums[mid]&&mid>0){
                mid--;
            }
        }
        System.out.println(mid);
        if(mid ==len/2){
            return binarySearch(nums,0,len-1,target);
        }

        if(target<=rightVal){
            return binarySearch(nums,mid,len-1,target);
        }else{
            return binarySearch(nums,0,mid,target);
        }

    }

    public int binarySearch(int[] nums,int left,int right,int target){
        int l = left;
        int r = right;
        while(l<=r){
            int mid = l+((r-l)/2);
            if(nums[mid]>target){
                r = mid-1;
            }else if(nums[mid]<target){
                l = mid+1;
            }else{
                return mid;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Leetcode33 leetcode33 = new Leetcode33();
        int[] a  =new int[]{5,1,2,3,4};
        int search = leetcode33.search(a, 1);
        System.out.println(search);
    }
}
